home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 July: Mac OS SDK / Dev.CD Jul 96 SDK / Dev.CD Jul 96 SDK1.toast / Development Kits (Disc 1) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc Source Code / Utilities / Interfaces / PriortyQ.h < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-22  |  1.7 KB  |  71 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        PriortyQ.h
  3.  
  4.     Contains:    Priority-Queue data structure.
  5.  
  6.     Owned by:    Jens Alfke
  7.  
  8.     Copyright:    © 1994 - 1995 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Theory of Operation:
  11.     
  12.     A Priority Queue is a sorted collection that allows entries to be added to
  13.     the queue in arbitrary order, and allows the first (in sort order) entry
  14.     -- and only the first entry -- to be viewed and removed. Its implementation
  15.     makes it very efficient, using a partially sorted data structure called a
  16.     heap. Any standard algorithms textbook will describe this; see Sedgewick's
  17.     "Algorithms in C++", ch.11.
  18. */
  19.  
  20.  
  21. #ifndef _PRIORTYQ_
  22. #define _PRIORTYQ_
  23.  
  24. #ifndef _ODTYPES_
  25. #include "ODTypes.h"
  26. #endif
  27.  
  28. #ifndef _PLFMDEF_
  29. #include "PlfmDef.h"
  30. #endif
  31.  
  32.  
  33. //=============================================================================
  34. // Queue-element mix-in class
  35. //=============================================================================
  36.  
  37. // Objects you put in the queue must inherit from this abstract mix-in class.
  38.  
  39. class Sortable {
  40.     public:
  41.         ODVMethod ODBoolean    ComesBefore( const Sortable* ) const
  42.             =0;
  43. };
  44.  
  45.  
  46. //=============================================================================
  47. // PriorityQueue
  48. //=============================================================================
  49.  
  50.  
  51. class PriorityQueue {
  52.     public:
  53.         PriorityQueue( ODULong suggestedSize =0 );
  54.         virtual ~PriorityQueue( );
  55.         
  56.         ODMethod    void        Add( const Sortable* );
  57.         ODMethod    Sortable*    GetFirst( ) const;
  58.         ODMethod    Sortable*    RemoveFirst( );
  59.         inline        void        RemoveAll( )        {fLast = 0;}
  60.         ODMethod    void        DeleteAll( );
  61.         
  62.         inline        ODBoolean    IsEmpty( ) const    {return fLast==0;}
  63.         
  64.     private:
  65.         ODULong        fSize;
  66.         ODULong        fLast;
  67.         const Sortable*    *fHeap;        // Points to array of Sortable*s
  68. };
  69.  
  70. #endif /*_PRIORTYQ_*/
  71.